 //
//  Graph.h
//  Graph Generator
//
//  Created by Emanuele Vespa on 2/10/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//  SPD Project
//

#ifndef Graph_Generator_Graph_h
#define Graph_Generator_Graph_h



#endif



#include <vector>
#include <list>
#include <queue>
#include <bitset>
#include <fstream>
#include <set>
#include <algorithm>
#include <time.h>
#include <limits>

#include "Edge.h"
#include "defines.h"

using namespace std;


int binary_search_edge(std::vector<int> vec, int low, int high, float value);


class CompareVertices {
    
public:
    bool operator()( const Vertex& v1, const Vertex& v2) const{
        
        
        if( v1.getKey() <= v2.getKey() ) return true;
        else return false;
        
    }
    
    
};


int binary_search_edge( std::vector<int> vec, int low, int high, float value){
    
    float mid_cost;
    int mid;
    
    if( low == high) return low;
    
    if ( low == high - 1 ) {
        
        mid_cost = (float) (vec[low] + vec[high]) / 2;
        if ( value > mid_cost ) return high;
        else return low;
        
        
    }
    
    mid = (high + low) / 2;
    
    
    if( value < vec[mid]) return binary_search_edge(vec,low, mid-1, value);
    if( value > vec[mid]) return binary_search_edge(vec, mid+1, high, value);
    if( value == vec[mid]) return mid;
    
    return 0;
    
}









class MultiGraph {
    
  
    
public:
    
    std::vector<Vertex> vertices; // vertices 
    std::vector<std::list<int> > contracted; // list of contracted nodes
    std::vector< int > nodes_degrees; // degree of the nodes
    
    int **matrix; // adjacency matrix



    std::vector<Edge> edges; 
    std::list<Edge > edge_list;
    std::list<int> weight_list;
    std::vector<std::list< std::pair<Vertex, int > > > adjacency_list;
    

    
    
    int vertexNum;
    int max_weight;
    int min_weight;
    int vertexCount;
    int iteration_min;
    
    pair<int, int> cut_vertices; // metavertices of the cut

    int cut_weight; // weight of the cut

    
    
    MultiGraph(){   // default constuctor
    
        vertexNum = 0;
        min_weight = numeric_limits<int>::max();
        max_weight = 0;
        cut_weight = 0;
        iteration_min = 0;
    }
    
    
    ~MultiGraph(){ // default destructor
        
              
        for (int i = 0; i < vertexNum; i++) {
            scalable_free(matrix[i]);
        }
        
        scalable_free(matrix);

        
    }

    
    MultiGraph(int dim) {  
        vertexNum = dim;
        min_weight = 100000;
        max_weight = 0;
        cut_weight = 0;
    
    }
    
    MultiGraph(MultiGraph const &g){    // copy constructor
        
        
        min_weight = g.min_weight;
        max_weight = g.max_weight;
        cut_weight = g.cut_weight;
        
        nodes_degrees = g.nodes_degrees;
        
        contracted = g.contracted;
        
        vertexNum = g.vertexNum;
        vertexCount = g.vertexCount;
        vertices = g.vertices;
        edges = g.edges;
        iteration_min = g.iteration_min;
        
                
        
        matrix = (int **) scalable_malloc(sizeof(int *) * g.vertexNum);
        
        for(int i = 0; i < g.vertexNum; i++){
            
            matrix[i] = (int *) scalable_malloc(sizeof(int) * g.vertexNum);
            
            for ( int j = 0; j < g.vertexNum; j++) {
                
                matrix[i][j] = g.matrix[i][j];
            }
            
        }
        
        
    }
    
    
    
    int copy(const MultiGraph &g){  // copy method
        
        min_weight = g.min_weight;
        max_weight = g.max_weight;
        cut_weight = g.cut_weight;
        
        nodes_degrees = g.nodes_degrees;
        
        contracted = g.contracted;
        
        vertexNum = g.vertexNum;
        vertexCount = g.vertexCount;
        vertices = g.vertices;
        edges = g.edges;
        
        iteration_min = g.iteration_min;
                
        
        for(int i = 0; i < g.vertexNum; i++){
            
            for ( int j = 0; j < g.vertexNum; j++) {
                
                matrix[i][j] = g.matrix[i][j];
            }
            
        }
        
        return 1;
        
    }
    
    
    // auxiliary methods
    
    void addEdge(Edge e);    
    void addVertex(Vertex v);
    void addList(std::list<Vertex> l);
    void setVertexNum(int num){ vertexNum = num; };
    void printGraph();
    bool isConnected();
    bool DFS();
    void generateMatrix(int dim);
    void saveMatrix(char * file_path);
    void printMatrix();
    void printMatrix(int iter, ofstream& f);
    
    
    // Karger's Min Cut Methods
    
    
    
    void readGraph(const char * file_path);
    int randChoose(vector<int> & );
    int randChoose( int * , int length );
    
    int randChoose(vector<int> &, unsigned short * );
    int randChoose( int * , int length, unsigned short * );
    void randContract(unsigned short *);

    void randContract();
    int KargerMinCut(int num_runs);
    int KargerMinCut(int num_runs, unsigned short *seed);

    int ParallelKarger();
    int ParallelKarger(int num_threads);
    
    int getCutPartitions(list< int >& s, list < int >& t);
    
    
   
    
    
    
};








void MultiGraph::addEdge(Edge e){
    
    edges.push_back(e);
    
}

void MultiGraph::addVertex(Vertex v){
    vertices.push_back(v);
}


void MultiGraph::addList(std::list<Vertex> l){
    
    
    
    
}

void MultiGraph::readGraph(const char * file_path){
    
    
    std::ifstream fp;
    int source, dest, cost;
    Vertex v1, v2;
    std::pair<Vertex, int> v;
    
    
    
    
    Edge e;
    std::list< std::pair <Vertex, int > > arcs;
              
    fp.open(file_path);
    
    if( fp.is_open()){
        
        
        
        
        fp >> vertexNum;
        
        vertexCount = vertexNum;
        
        
        matrix = (int **) scalable_malloc(sizeof(int *) * vertexNum);
        nodes_degrees.resize(vertexNum);
        contracted.resize(vertexNum);   
        
        for( int i = 0; i < vertexNum; i++ ) {
            
            matrix[i] = (int *) scalable_malloc (sizeof(int) * vertexNum);
            nodes_degrees[i] = 0;
                        
            for ( int j = 0; j < vertexNum; j++) matrix[i][j] = 0;
            
            contracted[i].push_back(i);
                                                
                     
        }
        
        
        
        for(int i = 0; i < vertexNum; i++){ // initialize adjacency list
            
            v1.setIndex(i);
            v.first = v1;
            v.second = 0;
            arcs.push_back(v);
            addVertex(v1);
            adjacency_list.push_back(arcs);
            arcs.clear();
            
            
        }   


        
        while (!fp.eof()) {
            
            
            
            fp >> source >> dest >> cost;
            
            if(cost > max_weight) max_weight = cost;
            if(cost < min_weight) min_weight = cost;
            
            matrix[source][dest] = cost;
            matrix[dest][source] = cost;
            
            
            

            
            v1.setIndex(source);
            v2.setIndex(dest);
            
            e.setVertices(v1, v2);
            e.setCost(cost);
            addEdge(e);
            
            v.first = v2;
            v.second = cost;
            
            adjacency_list[source].push_back(v);
            
            v.first = v1;
            v.second = cost;
            adjacency_list[dest].push_back(v);
            
            
        }
        
    }
    
    for(int i = 0; i < vertexNum; i++){
        
        for(int j = 0; j < vertexNum; j++){
            
            nodes_degrees[i] = nodes_degrees[i] + matrix[i][j];
            
        }
    }
    
   
}

void MultiGraph::generateMatrix(int dim){ // method for generating matrix
    
    std::ifstream fp;
    int source, dest, cost;
    float p;
    Vertex v1, v2;
    std::pair<Vertex, int> v;
    vertexNum = dim;
    
    vertexCount = vertexNum;
    
//    matrix = new int * [vertexNum];
    nodes_degrees.resize(vertexNum);
    contracted.resize(vertexNum);
    
    
    srand(time(NULL));
    
    
    Edge e;
    std::list< std::pair <Vertex, int > > arcs;
    
    
    for(int i = 0; i < dim; i++){ // initialize adjacency list
        
        v1.setIndex(i);
        
        addVertex(v1);
        
        v.first = v1;
        
        v.second = 0;
        arcs.push_back(v);
        adjacency_list.push_back(arcs);
        arcs.clear();
        
        
    }   
    
    for( int i = 0; i < vertexNum; i++ ) {
        
//        matrix[i] = new int[vertexNum];
        nodes_degrees[i] = 0;
        
        for ( int j = 0; j < vertexNum; j++) matrix[i][j] = 0;
        
        contracted[i].push_back(i);
        
        
    }

    
    
    for (int i = 0; i < dim; i++) {
       
        
        for (int j = 0; j <= i; j++) {
            
            
            p = (double)rand()/(double)RAND_MAX;
            
            if( p < 0.50 && i!=j){
                
                cost = rand()%100+1;
                
                matrix[i][j] = cost;
                matrix[j][i] = cost;
                
                nodes_degrees[i] += cost;
                nodes_degrees[j] += cost;
                
                source = i;
                dest = j;
                
                v1.setIndex(i);
                v2.setIndex(j);
                e.setVertices(v1, v2);
                e.setCost(matrix[i][j]);
                addEdge(e);
                
                
                v.first = v2;
                v.second = cost;
                
                adjacency_list[source].push_back(v);
                
                v.first = v1;
                v.second = cost;
                adjacency_list[dest].push_back(v);
                            
                
            }
            
            else matrix[i][j] = 0;
        }
        
        
    }
    
}



void MultiGraph::printGraph(){
    
    std::list<std::pair<Vertex, int > >::iterator it;
    
    std::cout << "Number of edges: " << edges.size() << std::endl;
    
       for (int i = 0; i < edges.size(); i++) {
     
     std::cout << "Source vertex: " << edges.at(i).getSource().getIndex() << " ";
     std::cout << "Destination vertex: " <<  edges.at(i).getDest().getIndex() << " Cost: " << edges[i].getCost() <<  std::endl;
     
     } 
    
    
}

void MultiGraph::saveMatrix(char * file_path){
    
    
    ofstream file;
    file.open(file_path);
    
    if(file.is_open()){
    
        file << vertexNum << endl;
        
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j <= i; j++) {
                
                if(matrix[i][j] != 0) file << i << " " << j << " " << matrix[i][j] << endl;
                
            }
            
        }
        
        file.close();
        
    }
        
        else {
            
            cout << "FILE NOT OPENED" << endl;
            
        }
    
    
}





bool MultiGraph::DFS(){
    
    std::queue<Vertex>  queue;
    std::list< std::pair<Vertex, int > >::iterator it;
    
    Vertex temp;
    int count = 1;
    
    for (int i = 0; i < vertexNum; i++ ) vertices[i].mark = false;
    
    temp = adjacency_list[0].front().first;
    
    vertices[temp.getIndex()].mark = true;
    
    queue.push(temp);
    
    while( queue.empty() != true){
        
        temp = queue.front();
        
        for (it = adjacency_list[temp.getIndex()].begin(); it != adjacency_list[temp.getIndex()].end() ; it++) {
            
            if( ! (vertices[(*it).first.getIndex()].mark) ){
                
                vertices[(*it).first.getIndex()].mark = true;
                count++;
                queue.push((*it).first);
                
            }
        }
        
        queue.pop();
        
        
    }
    
    
    std::cout << "Number of vertex explored : " << count << " | Number of vertex in the graph : " << vertexNum << std::endl;
    std::cout << "Number of edges : " << edges.size() << std::endl;
     
    
    
    return ( count == vertexNum ? true : false );
}



void MultiGraph::printMatrix(){
    
    
    for (int i = 0; i < vertexNum; i++) {
        for (int j = 0; j < vertexNum; j++) {
            std::cout << matrix[i][j] << " ";
            
        }
        std::cout << std::endl;
    }
    
    
}



void MultiGraph::printMatrix(int iter, ofstream& f){
    
    
    f << endl << endl << "ITERATION  " << iter << endl << endl;
    
    for (int i = 0; i < vertexNum; i++) {
        for (int j = 0; j < vertexNum; j++) {
            f << matrix[i][j] << " ";
            
        }
        f << std::endl;
    }
    
    f << endl << endl;
    
    
}


// RANDOM CHOOSE WITH GLOBAL BUFFER


int MultiGraph::randChoose(vector<int>& input){ // method for random selecting an integer proportionally to its weight
 
    int index = 0;
    int total = 0;
    
    for(int i = 0; i < input.size(); i++) total += input[i];
    
    
    int r = rand() % (total);
    
    for(int i = 0; i < input.size(); i++) {
        
       

        
        if( r < input[i] ) { index = i; break; }
        
        r -= input[i];
           
        
    }
    
          
    return index;
    
}


// RANDOM CHOOSE WITH GLOBAL BUFFER


int MultiGraph::randChoose( int * vec, int length){ 
    
  
    
    int index = 0;
    int total = 0;
    
    for(int i = 0; i < length; i++) total += vec[i];
    
    
    int r = rand() % (total);
    
    for(int i = 0; i < length; i++) {
        
        
        
        
        if( r < vec[i] ) { index = i; break; }
        
        r -= vec[i];
        
        
    }

    
        
        
    return index;
    
    
    
    
}


// RANDOM CHOOSE WITH INDEPENDENT BUFFERS
// The use of the independent buffer is required in a multithreaded enviroment

int MultiGraph::randChoose(vector<int>& input, unsigned short *buf){  
                                                                            
    int index = 0;
    int total = 0;
    
    for(int i = 0; i < input.size(); i++) total += input[i];
    
        
    long int r;
    
    r = nrand48(buf) % total;
    
    
    for(int i = 0; i < input.size(); i++) {
        
        
        if( r < input[i] ) { index = i; break; }
        
        r -= input[i];
        
        
    }

    
    return index;
    
    
}

// RANDOM CHOOSE WITH INDEPENDENT BUFFERS
// The use of the independent buffer is required in a multithreaded enviroment

int MultiGraph::randChoose( int * vec, int length, unsigned short *buf){
    
    
    int index = 0;
    int total = 0;
    
    for(int i = 0; i < length; i++) total += vec[i];
    
    
    long int r;
    
    r = nrand48(buf) % total;
    
       
    for(int i = 0; i < length; i++) {
        
        
        
        
        if( r < vec[i] ) { index = i; break; }
        
        r -= vec[i];
        
        
    }  
    
    
    return index;
    
    
}


// Finds a cut choosing at random edges to contract


void MultiGraph::randContract(){
    
    int u, v;
     
    while (vertexCount > 2) {
        
        
                
        u = randChoose(nodes_degrees);
        
        v = randChoose(matrix[u], vertexNum);

        
        
        nodes_degrees[u] = nodes_degrees[u] + nodes_degrees[v] - (2*(matrix[u][v]));
        nodes_degrees[v] = 0;
        matrix[u][v] = matrix[v][u] = 0;
        
        
        
        for( int w = 0; w < vertexNum; w++) {
            
            if( (w != u) && (w != v)){
                
                matrix[u][w] = matrix[u][w] + matrix[v][w];
                matrix[w][u] = matrix[w][u] + matrix[w][v];
                matrix[v][w] = matrix[w][v] = 0;
                
            }
            
        }
        
        contracted[u].splice(contracted[u].end(), contracted[v]); 
        
        
        vertexCount--;
        
    }    // end while
    
    
    
    cut_weight = 0;
    
    
    // Exctract from the contracted vector the two size of the cut
    
    for( int i = 0, j = 0; i < contracted.size() && j < 1; i++){
        
        if(! contracted[i].empty()){ u = i; j++; cut_vertices.first = u; }
    }
    
    
    for( int j = 0; j < vertexNum; j++){
        
        
        
        if ( matrix[u][j] != 0 ) cut_vertices.second = j;       
    }
    
    cut_weight = matrix[cut_vertices.first][cut_vertices.second];
    
       
    if(cut_weight != nodes_degrees[u]) cut_weight = -1; // extra control of correctness: the cut weight and the degree of the remaining node must be the same
    
}



// Finds a cut choosing at random edges to contract
// Takes as input the buffer for random number generation




void MultiGraph::randContract(unsigned short * buf){
    
    int u, v;
    
    while (vertexCount > 2) {
        
        
        
        u = randChoose(nodes_degrees, buf); // CHOOSE FIRST VERTEX
        
        v = randChoose(matrix[u], vertexNum, buf); // CHOOSE SECOND VERTEX
        
        
        
        nodes_degrees[u] = nodes_degrees[u] + nodes_degrees[v] - (2*(matrix[u][v]));
        nodes_degrees[v] = 0;
        matrix[u][v] = matrix[v][u] = 0;
        
        
        
        for( int w = 0; w < vertexNum; w++) {
            
            // SUM U AND V ROWS AND COLUMS
            // SET ROW AND COLUM V AT ZERO
            
            if( (w != u) && (w != v)){
                
                matrix[u][w] = matrix[u][w] + matrix[v][w];
                matrix[w][u] = matrix[w][u] + matrix[w][v];
                matrix[v][w] = matrix[w][v] = 0;
                
            }
            
        }
        
           contracted[u].splice(contracted[u].end(), contracted[v]); // MOVE THE CONTRACTED EDGE OF V TO U
        
        
        vertexCount--;
        
    }    // end while
    
    
    
    
    cut_weight = 0;
    
    for( int i = 0, j = 0; i < contracted.size() && j < 1; i++){
        
        if(! contracted[i].empty()){ u = i; j++; cut_vertices.first = u; }
    }
    
    
    for( int j = 0; j < vertexNum; j++){
        
        
        
        if ( matrix[u][j] != 0 ) cut_vertices.second = j;       
    }
    
    cut_weight = matrix[cut_vertices.first][cut_vertices.second];
    
    
    if(cut_weight != nodes_degrees[u]) cut_weight = -1;

    
    
        
}


// KARGER MIN-CUT WITH PARAMETRIC NUMBER OF RUNS


int MultiGraph::KargerMinCut( int num_runs ){
    
    MultiGraph * working_copy = new MultiGraph(*this); // ALLOCATE THE COPY WHERE TO RUN THE RANDCONTRACT ALGORITHM
    MultiGraph * min_cut_partial = new MultiGraph();
    int partial_minimum = numeric_limits<int>::max();
    
    
    
    for( int i = 0 ; i < num_runs; i++){
        

        if(i != 0 ) working_copy->copy(*this);

        
        
        working_copy->randContract();
        
        if( working_copy->cut_weight < partial_minimum) {
            
            min_cut_partial->cut_vertices = working_copy->cut_vertices;
            min_cut_partial->cut_weight = working_copy->cut_weight;
            min_cut_partial->contracted = working_copy->contracted;
            
            partial_minimum = working_copy->cut_weight;
            iteration_min = i;
            
        }
        
        
        
        
        
    }
    
   
    cut_weight = partial_minimum; 
    
    cut_vertices = min_cut_partial->cut_vertices;
    
    contracted = working_copy->contracted;
    
        
    
    return 1;
    
}


// KARGER MIN-CUT WITH PARAMETRIC NUMBER OF RUNS AND SEED FOR RANDOM THE NUMBER GENERATOR



int MultiGraph::KargerMinCut( int num_runs, unsigned short * seed ){
    
    MultiGraph * working_copy = new MultiGraph(*this);  // ALLOCATE THE COPY WHERE TO RUN THE RANDCONTRACT ALGORITHM
    MultiGraph * min_cut_partial = new MultiGraph();    // TEMPORARY PLACEHOLDER FOR PARTIAL MINIMUM
    int partial_minimum = numeric_limits<int>::max();
    
    
    
    for( int i = 0 ; i < num_runs; i++){
        
        
        if(i != 0 ) working_copy->copy(*this);
        
        
        
        working_copy->randContract(seed);
        
        if( working_copy->cut_weight < partial_minimum) {
            
            min_cut_partial->cut_vertices = working_copy->cut_vertices;
            min_cut_partial->cut_weight = working_copy->cut_weight;
            min_cut_partial->contracted = working_copy->contracted;
            
            partial_minimum = working_copy->cut_weight;
            
            iteration_min = i;
            
        }
        
        
        
        
        
    }
    
    
    cut_weight = partial_minimum; 
    
    cut_vertices = min_cut_partial->cut_vertices;
    
    contracted = working_copy->contracted;
    
    
    return 1;
    
}



int MultiGraph::getCutPartitions(list<int>& s, list<int>& t){
    
        
    s = contracted[cut_vertices.first];
    t = contracted[cut_vertices.second];
        
    
    return 1;
    
}







